A
讨论对于每一天吃饭需不需要洗餐具即可,优先使用盘子,其次使用碗,都没有就洗一个。
时间复杂度 。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m, k, ans, a[N];
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
if (a[i] == 1) m ? m-- : ans++;
if (a[i] == 2) k ? k-- : m ? m-- : ans++;
}
cout << ans << endl;
}
B
按照 的顺序安排,先求出 并安排 ,然后再安排 即可。
时间复杂度 ,注意 的特殊情况。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, k, l, r, S_all, S_k;
int a[N], S_res;
int main() {
ios::sync_with_stdio(false);
cin >> n >> k >> l >> r >> S_all >> S_k;
if (n != k) {
S_res = S_all - S_k;
for (int i = k + 1; i <= n; i++) a[i] = l;
S_res -= (n - k) * l;
for (int i = k + 1; i <= n; i++) a[i] += S_res / (n - k);
S_res %= (n - k);
for (int i = k + 1; i <= k + S_res; i++) a[i]++;
for (int i = 1; i <= k; i++) a[i] = a[k + 1];
S_k -= k * a[k + 1];
for (int i = 1; i <= k; i++) a[i] += S_k / k;
S_k %= k;
for (int i = 1; i <= S_k; i++) a[i]++;
} else {
for (int i = 1; i <= n; i++) a[i] = S_all / n;
S_all %= n;
for (int i = 1; i <= S_all; i++) a[i]++;
}
for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
}
C
维护一个答案集合 ,在搜索过程中维护修复根结点到 路径上所有问题边所需要选中的结点 ,如果边 为问题边则将 从 中删除并加入 。
时间复杂度 。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
struct edge {
int v, next, w;
edge(): v(0), next(0), w(0) {}
edge(int v, int next, int w): v(v), next(next), w(w) {}
} e[N];
int p[N], dep[N], n, eid;
set<int> st;
inline void insert(int u, int v, int w) {
e[eid] = edge(v, p[u], w);
p[u] = eid++;
}
void dfs(int u, int fa, int mn) {
for (int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if (v == fa) continue;
if (e[i].w) {
st.erase(mn);
st.insert(v);
dfs(v, u, v);
}
else dfs(v, u, mn);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
memset(p, -1, sizeof(p));
for (int i = 1; i <= n - 1; i++) {
int u, v, t;
cin >> u >> v >> t;
t--;
insert(u, v, t);
insert(v, u, t);
}
dfs(1, 1, 1);
cout << st.size() << endl;
for (int it : st) cout << it << " ";
}
D
注意到局面的改变只与编号最小的两个人有关,考虑dp。设 为幸存者编号最小值为 ,次小值为 的局面出现的最小轮数。
由于需要快速判断 是否有可能被后面的人打死,考虑维护 的后缀最大值 ,讨论最大值和最小值的更新方法,从而得到转移方程:
- 若 被打死且 存活,需要满足 且 ,此时有转移
- 若 打死 且 存活,需要满足 且 ,此时有转移
- 若 和 都被打死,需要满足 且 ,此时有转移
最后统计所有情况中最小轮数小于等于 的即可,时间复杂度 。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int f[N][N], p[N], suf[N], n, k, ans;
int main() {
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> p[i];
memset(f, 0x3f, sizeof(f));
for (int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], p[i]);
f[1][2] = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int v = f[i][j] + 1;
if (suf[j] && p[i] != 100) f[j][j + 1] = min(f[j][j + 1], v);
if (suf[j] && p[i]) f[j + 1][j + 2] = min(f[j + 1][j + 2], v);
if (suf[j] != 100 && p[i]) f[i][j + 1] = min(f[i][j + 1], v);
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n + 1; j++)
ans += (f[i][j] <= k);
}
cout << ans + (f[n + 1][n + 2] <= k) << endl;
}
E
待补。